A search is one of important technologies in the field of information processing, and there are various search methods corresponding to its use. As one of search methods, there is a longest prefix or suffix match search. A longest match search is often used for a character string having a hierarchical structure such as an address of the real world or URI (Uniform Resource Identifier) which indicates the location on the internet. For example, in the address as “X prefecture Y city,” an inclusion relation that “X prefecture” includes “Y city” is held. This shows that an address has a hierarchical structure.
Necessity of a longest match search is described. As an example, it is assumed that there is a database in which two areas as “A prefecture B city” and “A prefecture B city C ward” are registered. And consider finding an area closest to the address which is “A prefecture B city C ward XXX” from the database. Although both of above-mentioned two areas include the address, “A prefecture B city C ward” is more precise. In other words, number of characters which match with the address is larger in “A prefecture B city C ward” than in “A prefecture B city”.
A search method which searches a database for a pattern whose matching part is longest by matching the pattern with a search key from the beginning to the end of a character string as mentioned above is called a longest prefix match search. Also, a longest suffix match search is the same as a longest prefix match search except for matching is done from the end to the beginning of a character string.
As a technology which carries out the longest prefix or suffix match search, for example, there is one disclosed in patent document 1.
Here, operation of a technological example related to the present invention (hereinafter, referred to as a related technology example) is described using a drawing. An example which registers two registered patterns 100: “ABCDEFGHIJ” and “VWXYZ” in a database is shown in FIG. 28.
First, registered pattern 100 is divided into prefix 101 which is a first part and suffix 102 which is a latter part. “ABCDEFGHIJ” of registered pattern 100 is divided into prefix 101 of 8 characters and suffix 102 of 2 characters. Similarly, “VWXYZ” of registered pattern 100 is divided into prefix 101 of 4 characters and suffix 102 of 1 character. The length of prefix 101 is the number of characters of a multiple of predetermined value N (N is a natural number and indicates an interval of a dividing position) and is the largest length which does not exceed the length of registered pattern 100. In this example, it is supposed that N=4.
Next, for each registered pattern 100, hash value 103 is obtained by applying a hash function to prefix 101 and registered pattern 100 is added to a bucket of hash table 104 where the hash value 103 indicates. In this case, registered pattern 100 is separated into prefix 101 and suffix 102, and these are stored in hash table 104. When hash table 104 has a plurality of registered patterns 100 whose prefix 101 is common and suffix 102 is different, those suffixes 102 are connected in descending order of length as a linked list.
A search procedure when “VWXYZABCD” is given as search key 110 is shown in FIG. 29.
First, search key 110 is divided into prefix 111 and suffix 112 similar to the operation at the time of registration, and “VWXYZABC” of prefix 111 of 8 characters and “D” of suffix 112 of 1 character are obtained.
Next, hash value 113 is obtained by applying a hash function to prefix 111. This hash function is identical with one used at the time of registration. After that, it is examined whether or not one or more registered pattern 100 is stored in a bucket of hash table 104 where the hash value 113 indicates. Hash value 113 at this time is 2 and the bucket corresponding to it is empty. Accordingly, it is found that registered pattern 100 starting from “VWXYZABC” does not exist in the database.
Next, dividing position which divides prefix 111 and suffix 112 moves for N characters (N=4) to the left. In other words, prefix 111 is shortened by 4 characters and suffix 112 is lengthened by 4 characters. New prefix 111 is “VWXY” and new suffix 112 is “ZABCD”.
Next, after hash value 113 is obtained by applying the hash function to prefix 111, it is examined whether or not one or more registered pattern 100 is stored in a bucket of hash table 104 where the hash value 113 indicates. Hash value 113 at this time is 3 and “VWXYZ” of registered pattern 100 is stored in the bucket corresponding to it. When registered pattern 100 and search key 110 are matched, “VWXYZ” of registered pattern 100 matches with the first part of “VWXYZABCD” of search key 110. Accordingly, “VWXYZ” is a result of the longest prefix match search.